package com.ryujung.linked_list.lru;

import java.util.HashMap;
import java.util.Set;

/**
 * 设计LRU(Least Recently Used)的缓存数据结构
 * 算法介绍：
 * 最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
 * 
 * 分析：
 * LRU缓存的特点是：
 * 1. 缓存对象根据上次使用时间距离当前的长度排序，最近使用的排在最前面（排序）
 * 2. 缓存容量固定，当超过缓存容量时，会根据上次使用时间，自动淘汰掉最早被使用的缓存对象 （删除）
 * 3. 数据结构尽量复杂度要低，便于数据插入（新增）
 * 4. 键值对，类似于Map<String,Object>的使用方式
 * 5. 查找要快，当查找不到时，需要将当前查找的对象缓存到缓存队列的最前面
 * 
 * 首先可以想到的已知数据结构：
 * 1. HashMap ：插入、删除快，但是没有顺序，无法形成有序的缓存队列
 * 2. LinkedList：双向链表、有序、队首插入快，但查找复杂度O(n)，太慢
 * 
 * 具体实现：
 * 使用双向链表+哈希表的数据结构，实现查询（hash）和删除（linked）算法复杂度都为O(1)的LRU缓存数据结构。
 * 
 */
public class LruCache {

    public static void main(String[] args) {
        LruList cache = new LruList(3);
        System.out.println(cache);
        for (int j = 0; j < 2; j++) {
            for (int i = 0; i < 10; i++) {
                cache.put("key-" + i, "val-" + i);
                System.out.println(i + ":::" + cache);
            }
        }
        cache.get("key-" + 8);
        System.out.println(cache);
        cache.get("key-" + 7);
        System.out.println(cache);
    }

    /**
     * 链表元素
     */
    public static class Node {

        public Node pre;
        public Node next;
        public String key;
        public Object val;

        public Node(String key, Object val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return this.key + ":" + this.val;
        }

    }

    /**
     * 缓存链表队列
     */
    public static class LruList {

        private Node first;
        private Node last;

        public static final int DEFAULT_MAX_SIZE = 5;
        private HashMap<String, Node> internalMap = new HashMap<>();
        private int size;

        public LruList() {
            this.size = DEFAULT_MAX_SIZE;
        }

        public LruList(int size) {
            this.size = size <= 0 ? DEFAULT_MAX_SIZE : size;
        }

        public Node get(String key) {
            if (internalMap.containsKey(key)) {
                Node node = internalMap.get(key);
                remove(key);
                addFirst(node);
                return node;
            }
            return null;
        }

        public void put(String key, Object val) {
            Node node = new Node(key, val);
            if (!internalMap.containsKey(key) && internalMap.size() + 1 > size) {
                removeLast();
            }
            addFirst(node);
        }

        private void addFirst(Node t) {
            if (internalMap.containsKey(t.key)) {
                remove(t.key);
            } else {
                Node firstOld = this.first;
                if (firstOld != null) {
                    t.next = firstOld;
                    firstOld.pre = t;
                }
            }
            if (this.first != null) {
                this.first.pre = t;
            }
            this.first = t;
            if (internalMap.size() < 1) {
                this.last = t;
            }
            internalMap.put(t.key, t);
        }

        public void remove(String key) {
            if (internalMap.containsKey(key)) {
                Node node = internalMap.get(key);
                if (node.pre != null) {
                    node.pre.next = node.next;
                }
                if (node.next != null) {
                    node.next.pre = node.pre;
                }
                node.pre = null;
                node.next = null;
                internalMap.remove(key);
            }
        }

        public Node getFirst() {
            if (internalMap.size() <= 0) {
                return null;
            } else {
                return this.first;
            }
        }

        /**
         * 移除并返回最后一个元素
         * 
         * @return
         */
        public Node removeLast() {
            Node lastOld = this.last;
            if (lastOld != null) {
                internalMap.remove(lastOld.key);
                if (lastOld.pre != null) {
                    this.last = lastOld.pre;
                    this.last.next = null;
                    lastOld.pre = null;
                }
            }
            return lastOld;
        }

        public int size() {
            return internalMap.size();
        }

        public Set<String> keys() {
            return internalMap.keySet();
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("LruList[");
            Node node = this.first;
            while (node != null) {
                sb.append(node.toString()).append(",");
                node = node.next;
            }
            if (this.first != null) {
                sb.deleteCharAt(sb.lastIndexOf(","));
            }
            sb.append("]");
            return sb.toString();
        }

    }

}
